/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @see https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/submissions/
 * @param {ListNode} head
 * @return {ListNode}
 */
 var reverseList = function(head) {
  let arr = [head];
  while(head.next) {
    arr.push(head.next)
    head = head.next
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    let ele = arr[i];
    ele.next = arr[i - 1] || null;
  }
  head = arr[arr.length - 1];
  console.log(head.next.next)
};

/**
 * 链表
 * 1 > 2 > 3 > 4 > null
 * 第一轮循环 cur = 1, next = 2, pre = 1 => 
 * 第二轮循环 cur = 2, next = 3, pre = 1 =>
 * 第三轮循环 cur = 3, next = 4, pre = 2 =>
 * 第四轮循环 cur = 4, next = null, pre = 3
 * 第五轮循环 cur = null; 退出
 * 此时pre = 4 > 3 > 2 > 1 > null
 * @param {*} head 
 * @returns 
 */
var reverseList2 = function(head) {
  let pre = null, cur = head, next;
  while(cur != null) {
    next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  console.log(pre)
  return pre;
}

var reverseListDP = function(head) {
  console.log(head);
  if(!head || !head.next) {
    return head;
  }
  let node = reverseListDP(head.next);
  console.log('=======', head, head.next, node);
  head.next.next = head;
  head.next = null;
  return node;
}

var head = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: null
      }
    }
  }
}

reverseListDP(head);